Brain Teaser Puzzles

Polar bear puzzle

2012-11-12T21:44:00.000+05:30

Puzzle:

There is a house with four walls. Each wall faces south. There is a window in each wall.

A bear walks by one of the windows. What colour is the bear?

Solution:
White. If all the walls face south, the house is at the north pole, and the bear, therefore, is a polar bear.

Solution of Bridge crossing Riddle

2012-11-12T21:43:00.000+05:30

Solution:
-> 1. + 2. - 2 min
<- 1. - 1 min
-> 3. + 4. - 9 min
<- 2. - 2 min
-> 1. + 2. - 2 min

Total - 16 min
note:
-> forward direction
<- Reverse direction

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

Bridge crossing Riddle

2012-11-12T21:41:00.000+05:30

Question:
There are four people at the end of bridge. They take following time to cross the bridge:
1st: 1 min
2nd: 2 min
3rd: 7 min
4th: 9 min

Condition:
1. They have only one torch and they can't cross bridge without torch.
2. and only 2 person can cross bridge at a time.

Solution:
CLICK HERE

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

Solution of Burn the rope....good puzzle

2012-11-12T21:36:00.000+05:30

Solution:
Take 2 ropes R1, R2. Light R1 at both ends and R2 at one end. When R1 is completely burned (30 minutes have passed), light R2 at the other end. When R2 is completely burned 45 minutes have passed.

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

Burn the rope....good puzzle

2012-11-12T21:34:00.000+05:30

Question:
there are unlimited ropes of same length and if we burn them it will take 1 hour.
How to measure 45 mins?

Solution:
CLICK HERE

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

Solution of 100 door puzzle....microsoft interview puzzle

2012-11-12T21:31:00.000+05:30

Solution:

This problem is designed to seem overwhelming. You don’t have time to draw a diagram of 100 lockers and count 100 passes through them. Even if you did, solving the problem that way wouldn’t illustrate any skill or intuition, so there must be some trick that can be used to determine how many doors will be open. You just have to figure out what that trick is.

It’s unlikely that you’re going to be able to intuit the solution to this problem by just staring at it. What can you do? Although it’s not practical to solve the entire problem by brute force, solving a few lockers in this manner is reasonable. Perhaps you’ll notice some patterns you can apply to the larger problem.
Start by choosing an arbitrary locker, 12, and determining whether it will end open or closed. On which passes will you toggle locker 12? Obviously on the first pass, when you toggle every locker, and on the twelfth pass when you start with 12. You don’t need to consider any pass after 12 because those will all start farther down the hall. This leaves passes 2 through 11. You can count these out: 2, 4, 6, 8, 10, 12 (you toggle on pass 2); 3, 6, 9, 12 (on 3); 4, 8, 12 (on 4); 5, 10, 15 (not on 5); 6, 12 (on 6); 7, 14 (not on 7), and so on. Somewhere in the middle of this process, you will probably notice that you toggle locker 12 only when the number of the pass you’re on is a factor of 12. If you think about this, it makes sense: When counting by n, you hit 12 only when some integer number of n’s add to 12, which is another way of saying that n is a factor of 12. Though it seems simple in retrospect, this probably wasn’t obvious before you worked out an example.
The factors of 12 are 1, 2, 3, 4, 6, and 12. Correspondingly, the operations on the locker door are open, close, open, close, open, close. So locker 12 will end closed. The solution seems to have something to do with factors. Primes are numbers with unique factor properties. Perhaps it would be instructive to investigate a prime numbered locker. You might select 17 as a representative prime. The factors are 1 and 17, so the operations are open, close. It ends closed just like 12. Apparently primes are not necessarily different from nonprimes for the purposes of this problem.

What generalizations can you make about whether a locker ends open or closed? All lockers start closed and alternate between being open and closed. So lockers are closed after the second, fourth, sixth, and so on, times they are toggled - in other words, if a locker is toggled an even number of times, then it ends closed; otherwise, it ends open. You know that a locker is toggled once for every factor of the locker number, so you can say that a locker ends open only if it has an odd number of factors.

The task has now been reduced to finding how many numbers between 1 and 100 have an odd number of factors. The two you’ve examined (and most others, if you try a few more examples) have even numbers of factors. Why is that? If a number i is a factor of n, what does that mean? It means that i times some other number j is equal to n. Of course, because multiplication is commutative (i × j = j × i), that means that j is a factor of n, too, so the number of factors is usually even because factors tend to come in pairs. If you can find the numbers that have unpaired factors, you will know which lockers will be open. Multiplication is a binary operation, so two numbers will always be involved, but what if they are both the same number (that is, i = j)? In that case, a single number would effectively form both halves of the pair and there would be an odd number of factors. When this is the case, i × i = n. Therefore, n would have to be a perfect square. Try a perfect square to check this solution. For example, for 16, the factors are 1, 2, 4, 8, 16; operations are open, close, open, close, open - as expected, it ends open.

Based on this reasoning, you can conclude that only lockers with numbers that are perfect squares end open. The perfect squares between 1 and 100 (inclusive) are 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100. So 10 lockers would remain open.

Similarly, for the general case of k lockers, the number of open lockers is the number of perfect squares between 1 and k, inclusive. How can you best count these? The perfect squares themselves are inconvenient to count because they’re unevenly spaced. However, the square roots of the perfect squares greater than zero are the positive integers. These are very easy to count: The last number in the list of square roots gives the number of items in each list. For example, the square roots of 1, 4, 9, 16, and 25 are 1, 2, 3, 4, and 5; the last number in the list of square roots is the square root of the largest perfect square and is equal to the number of perfect squares. You need to find the square root of the largest perfect square less than or equal to k.

This task is trivial when k is a perfect square, but most of the time it won’t be. In these cases, the square root of k will be a noninteger. If you round this square root down to the nearest integer, then its square is the largest perfect square less than k-just what you were looking for. The operation of rounding to the largest integer less than or equal to a given number is often called floor. Thus, in the general case of k lockers, there will be floor(sqrt(k)) lockers remaining open.

The key to solving this problem is trying strategies to solve parts of the problem even when it isn’t clear how these parts will contribute to the overall solution. Although some attempts, such as the investigation of prime numbered lockers, may not be fruitful, others are likely to lead to greater insight about how to attack the problem, such as the strategy of calculating the result for a single locker. Even in the worst case, where none of the things you try lead you closer to the final solution, you show the interviewer that you aren’t intimidated by difficult problems with no clear solution and that you are willing to keep trying different approaches until you find one that works.

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

Solution of 2 Egg Problem: Google Interview Puzzle

2012-11-12T21:27:00.000+05:30

Solution:

Drop the first egg from 50.If it breaks you can try the same approach for a 50-storey building (1 to 49) and try it from 25th floor. If it did not break try at 75th floor. And use linear search with the remaining portion of storey we need to test. For example if the first egg breaks at 50 we need to try all possibilities from 1 to 49.

Now this looks a feasible solution. In computer student's jargon do a binary search with first egg and linear search with the second one. Best case is log (100) and worst is 50.

Now the optimal solution for the problem is that you figure out that you will eventually end up with a linear search because you have no way of deciding the highest floor with only one egg (If you broke one egg and you have to find the answer among 10 all you can do is start from the lowest to the highest and the worst is the total number of floors). So the whole question grinds up to how to make use of the first egg to reduce the linear testing of the egg.

(For strict computer science students, well this problem can be solved using binary search on the number of drops needed to find the highest floor.)

Now let x be the answer we want, the number of drops required.

So if the first egg breaks maximum we can have x-1 drops and so we must always put the first egg from height x. So we have determined that for a given x we must drop the first ball from x height. And now if the first drop of the first egg doesn’t breaks we can have x-2 drops for the second egg if the first egg breaks in the second drop.

Taking an example, lets say 16 is my answer. That I need 16 drops to find out the answer. Lets see whether we can find out the height in 16 drops. First we drop from height 16,and if it breaks we try all floors from 1 to 15.If the egg don’t break then we have left 15 drops, so we will drop it from 16+15+1 =32nd floor. The reason being if it breaks at 32nd floor we can try all the floors from 17 to 31 in 14 drops (total of 16 drops). Now if it did not break then we have left 13 drops. and we can figure out whether we can find out whether we can figure out the floor in 16 drops.

Lets take the case with 16 as the answer

1 + 15 16 if breaks at 16 checks from 1 to 15 in 15 drops
1 + 14 31 if breaks at 31 checks from 17 to 30 in 14 drops
1 + 13 45 .....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 We can easily do in the end as we have enough drops to accomplish the task

Now finding out the optimal one we can see that we could have done it in either 15 or 14 drops only but how can we find the optimal one. From the above table we can see that the optimal one will be needing 0 linear trials in the last step.

So we could write it as

(1+p) + (1+(p-1))+ (1+(p-2)) + .........+ (1+0) >= 100.

Let 1+p=q which is the answer we are looking for

q (q+1)/2 >=100

Solving for 100 you get q=14.
So the answer is: 14
Drop first orb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100).

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

Solution of Village of demons & sleeping man puzzle....tricky puzzle

2012-11-12T21:21:00.000+05:30

Solution:

1 demon 1 human
demon eat human.
2 demon 1 human
nothing happens.

3 demon 1 human
one demon eat the human.
Explanation:
if there are odd number of eaters and one sleeping target, one of the eater(demon) will eat the target(sleeping demon/man).

if eaters are even(>=2) nothing will happen because if he eat the target he will become the target,Now eaters will be odd and according to first case target will be eaten, so nobody of demons want to become target so nobody eat.

So 65+1
one demon eats the sleeping man.
nothing happens after that.

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

Village of demons & sleeping man puzzle....tricky puzzle

2012-11-12T21:17:00.000+05:30

Question:

given a village with demons and a sleeping man, The man is always sleeping ,never wakes up. Now a demon can eat the sleeping man , but after that
he will fall asleep , any demon can eat another sleeping demon.

If demons are very smart and would always choose to stay alive than to eat the man and risk their lives.
so if initially there are 65 demons and 1 sleeping man .. what would happen in the village ??

Solution:

CLICK HERE

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

Find bad apples from boxes in 1 attempt...!!!

2012-11-12T21:07:00.000+05:30

Question:
There are 10 boxes of apples. Each apple in the boxes weights 1 pound, except that one of the boxes contains bad apples, which weights 0.9 pound each. You are given a digital weight (not a scale), and you can take apples out of the boxes. what is the minimum time of weighs to find out which box has bad apples?

Solution:

it's simple:
take 1 apple from box 1, 2 apples from box 2 ... 10 apples from box 10
put all on scale, say it shows XX.Y pounds

look at Y (fractional part).
if it's 0, it's box 10
1 - box 9
2 - box 8
...
9 - box 1

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

Move block in matrix

2012-11-12T20:57:00.000+05:30

Question:
Given a m*n matrix and a person is sitting in (0,0) box, and he has to go to the (m-1,n-1) box of the matrix .And the person can only go to right or down box from its current box position . We need to find out the number of ways he can reach from start to destination box .

Solution:
He needs to take total 'm-1 down' + 'n-1 right' steps

Its classical Permutation and Combination problem.
Refer to theorem 3 on this page intmath.com/counting-probability/3-permutations.php

Hence ans = (m+n-2)! / ((m-1)!*(n-1)!)

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

100 prisoner`s hat problem..

2012-11-12T20:56:00.000+05:30

Question:
There are 100 prisoners , and a officer of them . Now the officer gave the command to the prisoner that next day they will be going to wear a hat which they will not be know its colour . But its colour will be either Red or Blue . And he says that all the prisoner will be standing in a line .
And then the officer will start asking the color of the prisoner one by one from the back . whichever prisoner says the wrong color of his hat ,gets shoot .So now we have to find out wat strategy should the prisoners should apply to safe maximum prisoners .

Solution:
The one in the back will just say which color occurs even number of times. Than all th rest can figure out what his color is. The one in the back will die with %50 probability rest will survive for sure.

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

Google letter/number series puzzle

2012-11-12T20:54:00.000+05:30

Puzzle:

Fill in the blanks:

--   --  --  H  I   K  L   M   N  T
     --   --  --  G  J  O  P  Q   R  S

Answer:
hint:Characters in the top row are written with straight lines, whereas those in the bottom row are written with curved lines.

1) This pattern perfectly fits with the first 6 characters.
A E F
B C D

2) b c f

a d e
One way of looking at this is by taking the numbers equivalent to these alphabets. if we replace the existing series of alphabets with the numbers equivalent to these alphabets, then we'll see something like this

8 9 11 12 13 14 20
7 10 15 16 17 18 19

there are multiple ways of looking at it, I found that given a number, the double of the number never comes in the same line, and used this logic to crack the first 6 positions. There might be other ways of looking at it.

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

find random number between 1-7

2012-11-12T20:52:00.000+05:30

Question:
Given a random number generator say r(5) generates number between 1-5 uniformly at random , use it to in r(7) which should generate a random number between 1-7 uniformly at random.

Solution:

int rand7() //random number from 1 - 7
{
    int r = 0;
    do
    {
       int a = rand(5) - 1; //uniformly at random from 0 to 4
       int b = rand(5) - 1;  //uniformly at random from 0 to 4
       r = 5*b + a;  //uniformly at random from 0 to 24
    }
    while (r >= 21); // in this event, we have to roll again
   //postcondition of loop: we have a number uniformly at random between 0 and 20

return r % 7 + 1; 





//there are 3 numbers in [0, 20] for each possible return value



//so each has equal probability.      



} 













POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

17 min bridge crossing puzzle

2012-11-12T20:47:00.000+05:30

Puzzle:
There are four people who want to cross a bridge; they all begin on the same side. You have 17 minutes to get them all across to the other side. It is night, and they have one flashlight. A maximum of two people can cross the bridge at one time. Any party that crosses, either one or two people, must have the flashlight with them.
The flashlight must be walked back and forth; it cannot be thrown, for example. Person 1 takes 1 minute to cross the bridge, person 2 takes 2 minutes, person 3 takes 5 minutes, and person 4 takes 10 minutes. A pair must walk together at the rate of the slower person’s pace. For example, if person 1 and person 4 walk across first, 10 minutes have elapsed when they get to the other side of the bridge. If person 4 returns the flashlight, a total of 20 minutes have passed and you have failed the mission.

Solution:
1+2 : 2 min
1 back : 1 min
3+4 : 10 min
2 back : 2 min
1+2: 2 min

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

What are your weaknesses? (HR interview)

2012-11-12T20:42:00.000+05:30

TRAPS: Beware - this is an eliminator question, designed to shorten the candidate list. Any admission of a weakness or fault will earn you an “A” for honesty, but an “F” for the interview.

PASSABLE ANSWER:

Disguise a strength as a weakness.

Example: “I sometimes push my people too hard. I like to work with a sense of urgency and everyone is not always on the same wavelength.”

Drawback: This strategy is better than admitting a flaw, but it's so widely used, it is transparent to any experienced interviewer.

BEST ANSWER:
(and another reason it's so important to get a thorough description of your interviewer's needs before you answer questions):
Assure the interviewer that you can think of nothing that would stand in the way of your performing in this position with excellence. Then, quickly review you strongest qualifications.
Example: “Nobody's perfect, but based on what you've told me about this position, I believe I' d make an outstanding match. I know that when I hire people, I look for two things most of all. Do they have the qualifications to do the job well, and the motivation to do it well? Everything in my background shows I have both the qualifications and a strong desire to achieve excellence in whatever I take on. So I can say in all honesty that I see nothing that would cause you even a small concern about my ability or my strong desire to perform this job with excellence.”

Alternate strategy
(if you don't yet know enough about the position to talk about such a perfect fit):
Instead of confessing a weakness, describe what you like most and like least, making sure that what you like most matches up with the most important qualification for success in the position, and what you like least is not essential.

Example:

Let's say you're applying for a teaching position. “If given a choice, I like to spend as much time as possible in front of my prospects selling, as opposed to shuffling paperwork back at the office. Of course, I long ago learned the importance of filing paperwork properly, and I do it conscientiously. But what I really love to do is sell (if your interviewer were a sales manager, this should be music to his ears.)

What are your greatest strengths? (HR interview)

2012-11-12T20:39:00.000+05:30

TRAPS: This question seems like a softball lob, but be prepared. You don't want to come across as egotistical or arrogant. Neither is this a time to be humble.

BEST ANSWER: You know that your key strategy is to first uncover your interviewer's greatest wants and needs before you answer questions. And from Question 1, you know how to do this.

Prior to any interview, you should have a list mentally prepared of your greatest strengths. You should also have, a specific example or two, which illustrates each strength, an example chosen from your most recent and most impressive achievements.

You should, have this list of your greatest strengths and corresponding examples from your achievements so well committed to memory that you can recite them cold after being shaken awake at 2:30AM.
Then, once you uncover your interviewer's greatest wants and needs, you can choose those achievements from your list that best match up.
As a general guideline, the 10 most desirable traits that all employers love to see in their employees are:

1. A proven track record as an achiever...especially if your achievements match up with the employer's greatest wants and needs.

2. Intelligence...management "savvy".

3. Honesty...integrity...a decent human being.

4. Good fit with corporate culture...someone to feel comfortable with...a team player who meshes well with interviewer's team.

5. Likeability...positive attitude...sense of humor.

6. Good communication skills.

7. Dedication...willingness to walk the extra mile to achieve excellence.

8. Definiteness of purpose...clear goals.

9. Enthusiasm...high level of motivation.

10. Confident...healthy...a leader.

Tell me about yourself (HR interview)

2012-11-12T19:46:00.000+05:30

TRAPS: Beware, about 80% of all interviews begin with this “innocent” question. Many candidates, unprepared for the question, skewer themselves by rambling, recapping their life story, delving into ancient work history or personal matters.

BEST ANSWER:

Start with the present and tell why you are well qualified for the position. Remember that the key to all successful interviewing is to match your qualifications to what the interviewer is looking for. In other words you must sell what the buyer is buying. This is the single most important strategy in job hunting.

So, before you answer this or any question it's imperative that you try to uncover your interviewer's greatest need, want, problem or goal.

To do so, make you take these two steps:

1. Do all the homework you can before the interview to uncover this person's wants and needs (not the generalized needs of the industry or company)

2. As early as you can in the interview, ask for a more complete description of what the position entails. You might say: “I have a number of accomplishments I'd like to tell you about, but I want to make the best use of our time together and talk directly to your needs. To help me do, that, could you tell me more about the most important priorities of this position? All I know is what I (heard from the recruiter, read in the classified ad, etc.)”

Then, ALWAYS follow-up with a second and possibly, third question, to draw out his needs even more. Surprisingly, it's usually this second or third question that unearths what the interviewer is most looking for.
You might ask simply, "And in addition to that?..." or, "Is there anything else you see as essential to success in this position?:
This process will not feel easy or natural at first, because it is easier simply to answer questions, but only if you uncover the employer's wants and needs will your answers make the most sense. Practice asking these key questions before giving your answers, the process will feel more natural and you will be light years ahead of the other job candidates you're competing with.
After uncovering what the employer is looking for, describe why the needs of this job bear striking parallels to tasks you've succeeded at before. Be sure to illustrate with specific examples of your responsibilities and especially your achievements, all of which are geared to present yourself as a perfect match for the needs he has just described.

9 card puzzle

2012-11-12T19:41:00.000+05:30

Question:
9 cards are there. u have to arrange them in a 3*3 matrix.
cards are of 4 colors.they are red,yellow,blue,green.
conditions for arrangement: one red card must be in first row
or second row.2 green cards should be in 3rd column.Yellow
cards must be in the 3 corners only. Two blue cards must be in
the 2nd row. Atleast one green card in each row.

Solution:
Yellow Red Green
Blue Blue Green
Yellow Green Yellow

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

100 door puzzle....microsoft interview puzzle

2012-11-12T19:38:00.000+05:30

Question:
Lets say you have a room with 100 doors in it. Initially, all of these doors are open. You have 100 people that will be entering the room. The 1st person toggles every door, 2nd person toggles every other door, 3rd toggles every 3rd door, ... , nth person toggles every nth door. How would you determine the state of all 100 doors after all 100 people have entered the room?

Solution:
CLICK HERE

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

1000 barrels Puzzle

2012-11-12T19:36:00.000+05:30

Question:
A king is about to give a party in 24 hours. For the party they have arranged drinks which will be served through 1000 barrels. Out of jealousy , some one near to king has poisoned one of the barrels. The poison is so strong that even a drop can kill a person. But results are not immediate. A person may die from 13 to 20 hrs. Now king has a duty of finding that barrel. He has 24 hours with him. And he has unlimited prisoners on which the drinks can be tested. Find out the maximum prisoners he would need to find out that barrel.

Solution:
1) let's say you are identifying 4 barrels - you need two prisoners - you can mix the wine (or whatever it is) in such a way that either first prisoner dies, second prisoner dies, both die or none die, identifying the right barrel.

Let's say there are eight barrels. Let's number them 1 through 8. You need just three prisoners. First prisoner gets a mixture of 1, 2, 3, 4, second 3, 4, 5, 6 and third gets 1, 3, 5, 7. There are exactly eight combinations of the three prisoners dying or staying alive and with the above mixture each combination of the prisoner's deaths shows exactly which barrel was poisoned.

With 16 barrels you would need 4 prisoners.

The point is that with N prisoners you can 'encode' 2 to the N-th power barrels. With 1000 barrels you would need 10 prisoners.

2) 10 is the correct answer. consider the following

nC0 + nC1 +... +nCn= 2 power n
So upto 1024 barrels can be covered using upto 10 prisoners.
Think it like this. 1 drop from each barrel to ten prisoners. Then 11th barrel will be for both 1st and 2nd prisoner. 12th for 3rd and 4th prisoner. If they both die then this 11th barrel was poisened one. Keep making such combinations for all the barrels and considering all these 10 prisoners.

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

2 dice puzzle

2012-11-12T19:33:00.000+05:30

Question:
You are given 2 dice. Both are fair. One of the dice has no numbers printed on it. You have to label the unmarked dice such that when both the dice are thrown, the sum on the faces is evenly distributed between 1 and 12.

Solution:
Three 0s and three 6s.

Well imagine case of 2 normal dice. The sums will be between 2-12 when you throw them. Also 2 will come less times ( 1 + 1) while 7 would come more times ( 4 + 3 , 3 + 4, 5 + 2, 2+5), therefore this is not even distribution.

You have to make sure that the probability of each number between 1-12 is equal. Having 3 faces 0 and 3 faces 6 does that. Calculate by yourself

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

count the number of students in a classroom in quickest way

2012-11-12T19:28:00.000+05:30

Question:

How will you count the number of students in a classroom in quickest possible manner.

Solution:
Ask the class to stand up and make pairs, if one student is left out write '1' else write 0. tell the left out student to sit down and ask one person in each group to sit down. Repeat the process and append '1' or '0' to your number, until no student is left standing. You will get the binary representation of the number of students in reverse order.

Eg: lets say there are 23 students in the class
Students standing 23 11 5 2 1 0
Solution 1 1 1 0 1 0

we have a string 111010, and the binary representation of 23 is 010111.
This is just using divide and conquer O(lg n)

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

Find shortest path in an array

2012-11-12T19:25:00.000+05:30

Question:
Given a character array. Find if there exists a path from O to X. Here is an example

. . . . . . .
. . . . . . .
w . . . . . .
w .w.w..
. . . . O . .
. . w. . . .
. . . X . . .

You have to just keep in mind that you cannot go through 'W'.

Solution:
This can be solved by Simple Depth First Search using Recursion..
// 8 Adjacent points



int dx[]={+0,+0,+1,-1,+1,+1,-1,-1};



int dy[]={+1,-1,+0,+0,+1,-1,+1,-1};


bool visited[50][50];



string grid[50];



int m=50,n=50;



bool dfs(int x,int y){



if(grid[x][y]=='X')return 1;








bool res=0;



visited[x][y]=1;



for(int i=0;i<8;i++){



int newx=x+dx[i];



int newy=y+dy[i];



// Check whether the new point is valid one ..



if(newx>=0 && newy>=0 && newx<m && newy<n){



// Check whether it is visited already / it is not 'W'



if(visited[newx][newy]==0 && grid[x][y]!='W')



res|=(dfs(newx,newy));



}



}



return res;



}



bool solve(){



int startx=0,starty=0;



for(int i=0;i<m;i++){



for(int j=0;j<n;j++){



if(grid[i][j]=='O'){



startx=i,starty=j;



break;



}



}



}



return dfs(startx,starty);



}

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION

Obtain 4 litre from 5 & 3 litre jar

2012-11-12T19:21:00.001+05:30

Question:
There are 2 jars 5 lit and 3 lit capacity
measure 4 lit using them

Solution:
1)first fill 3L jar and empty it in 5L jar.
again fill 3L and empty it in 5L jar.
5L jar will be completely filled with 1L left in 3L jar.
empty 5L jar and then empty 3L jar in 5L jar
now refill 3L jar and empty it in 5L jar.
now 5L jar will contain 4 L (3+1)

2)fill 5 ltr jar and pour it in 3 ltr, so 2 ltr remains in 5 ltr jar.
Empty 3 ltr jar and pour 2 ltr from 5 ltr jar into it.
Now fill 5 ltr jar again and use it to fill remaining 1 ltr in 3 ltr jar. that keeps 4 ltr in 5 ltr jar

POST YOUR OPINION IF YOU HAVE BETTER SOLUTION